﻿# !/usr/bin/env python
# -*- coding: utf-8 -*-

'''
	Name: pseudo1.py
	Author: David Palma, 12054
	Description: Gerador de numeros Pseudo-Aleatórios
	Programa realizado na linguagem Python

	Opcoes de linha de comandos: python pseudo1.py [k]
	em que k eh a quantidade de numeros pretendidos 

	Beja, 8 de Fevereiro de 2012

	Estatisticas(segundos):
	Maquina Virtual VMWare Player: Mint 12 Gnome 32 bits
	Intel C2D 8600@2.4Ghz

	1000: 0.01
	10 000: 0.05
	100 000: 0.42
	1 000 000 000: 4.29
	10 000 000 000: 45.34
	100 000 000 000: nao testado
'''

# Utilizacao de arrays mais eficientes do que listas em Python
from array import array
import random
import sys
import time

# Interpreta a opcao do utilizador; Caso nao especifique, k = 1
k = int(sys.argv[1]) if (len(sys.argv) == 2) else 1

# Tempo do inicio da execucao do programa
t1 = time.clock()

'''
	Cria tabela T com 1000 entradas
	Inicializa a tabela com valores entre 0 e 9
'''
def init_table(T):
    # Tabela de 10 elementos com as frequencias dos digitos
    count = array('H', 10*[0])
   
	# Inicializacao da tabela com 1000 entradas
    for i in range(1000):
        while True:
            r = random.randint(0, 9)
            if count[r] < 100:
                break
            pass
        T[i] = r
        count[r] += 1
        pass
    return

'''
	Gera numero aleatorio Nk
'''
def gen_number(T, p, z):

    for i in range(4):
        l = p+i if p < (1000-i) else 0
        z[i] = T[l]
        T[l] = T[0]
        T[0] = z[i]
        pass

	# Formacao de Nk a partir de z utilizando Shift binario
    N = z[0] << 12 | z[1] << 8 | z[2] << 4 | z[3]
	# Formacao do valor p a ser utilizado nas proximas iteracoes
    p = z[0]*100 + z[1]*10 + z[2]
    return N

# Declaracao de variaveis
T = array('H', 1000*[0])
z = array('H', 4*[0])
   
# 1. Criar tabela T com 1000 entradas
init_table(T)

# 2. Gerar numero aleatorio no intervalo [0;999]
p = random.randint(0, 999)

# 3. Gerar numero aleatorio Nk, com k = numero de interacoes
for i in range(k):
    N = gen_number(T, p, z)
    pass

t2 = time.clock()

print "Tempo de execucao total: {0}".format(t2-t1)
